/// Represents the type of the binomial heap.
#[derive(Debug, Clone)]
pub enum BinomialHeapType {
    /// A minimum heap.
    Min,
    /// A maximum heap.
    Max,
}

/// Represents a binomial tree in a binomial heap.
#[derive(Debug, Clone)]
pub struct BinomialTree<T> {
    /// The value stored in the tree.
    pub value: T,
    /// The order of the binomial tree.
    pub order: u16,
    /// The subtrees of the binomial tree.
    pub subtrees: Vec<Box<BinomialTree<T>>>,
}

/// Represents a binomial heap data structure.
#[derive(Debug, Clone)]
pub struct BinomialHeap<T> {
    /// The type of the binomial heap (Min or Max).
    pub heap_type: BinomialHeapType,
    /// The number of values in the heap.
    pub num_values: u32,
    /// The roots of the binomial trees in the heap.
    pub roots: Vec<Option<Box<BinomialTree<T>>>>,
}

impl<T> BinomialTree<T> {
    /// Decreases the reference count of the binomial tree.
    /// If the reference count reaches zero, the tree and its subtrees are dropped.
    pub fn unref(&mut self) {
        // In Rust, the reference count is managed by the ownership system,
        // so we don't need to manually decrement a refcount.
        // Instead, we rely on the Drop trait to automatically clean up the tree.
        // When the tree goes out of scope, its subtrees will also be dropped.
    }
}

impl<T> BinomialHeap<T> {
    /// Returns the number of values in the heap.
    pub fn num_values(&self) -> u32 {
        self.num_values
    }
}

impl<T> BinomialHeap<T> {
    /// Creates a new binomial heap with the specified type.
    ///
    /// # Parameters
    /// - `heap_type`: The type of the binomial heap (Min or Max).
    ///
    /// # Returns
    /// Returns an `Option<BinomialHeap<T>>` representing the newly created heap.
    /// If memory allocation fails, returns `None`.
    pub fn new(heap_type: BinomialHeapType) -> Option<Self> {
        Some(BinomialHeap {
            heap_type,
            num_values: 0,
            roots: Vec::new(),
        })
    }
}

impl<T: Ord> BinomialHeap<T> {
    /// Merges two binomial trees into a new binomial tree.
    /// The new tree's root is the smaller of the two roots, and the larger tree becomes a subtree.
    /// Returns `None` if the merge fails due to allocation errors.
    pub fn binomial_tree_merge(
        &self,
        tree1: Box<BinomialTree<T>>,
        tree2: Box<BinomialTree<T>>,
    ) -> Option<Box<BinomialTree<T>>> {
        let (mut tree1, mut tree2) = if tree1.value > tree2.value {
            (tree2, tree1)
        } else {
            (tree1, tree2)
        };

        let new_order = tree1.order + 1;
        let mut new_tree = Box::new(BinomialTree {
            value: tree1.value,
            order: new_order,
            subtrees: Vec::with_capacity(new_order as usize),
        });

        new_tree.subtrees.extend(tree1.subtrees);
        new_tree.subtrees.push(tree2);

        Some(new_tree)
    }
}

impl<T: Ord> BinomialHeap<T> {
    /// Merges another heap into this heap.
    ///
    /// # Parameters
    /// - `other`: The other heap to merge into this one.
    ///
    /// # Returns
    /// Returns `true` if the merge was successful, `false` otherwise.
    pub fn merge(&mut self, other: &mut BinomialHeap<T>) -> bool {
        self.roots.append(&mut other.roots);
        self.num_values += other.num_values;
        // TODO: Implement proper merging of binomial trees of the same order
        true
    }

    /// Inserts a value into the binomial heap.
    ///
    /// # Parameters
    /// - `value`: The value to be inserted.
    ///
    /// # Returns
    /// Returns `true` if the insertion was successful, `false` otherwise.
    pub fn insert(&mut self, value: T) -> bool {
        // Create a new binomial tree of order 0
        let new_tree = Box::new(BinomialTree {
            value,
            order: 0,
            subtrees: Vec::new(),
        });

        // Create a fake heap for merging
        let mut fake_heap = BinomialHeap {
            heap_type: self.heap_type.clone(),
            num_values: 1,
            roots: vec![Some(new_tree)],
        };

        // Merge the fake heap with the current heap
        if self.merge(&mut fake_heap) {
            true
        } else {
            false
        }
    }
}

impl<T: Ord> BinomialHeap<T> {
    /// Pops the smallest (or largest) value from the binomial heap.
    ///
    /// # Returns
    /// Returns `Some(T)` if the heap is not empty, otherwise returns `None`.
    pub fn pop(&mut self) -> Option<T> {
        if self.num_values == 0 {
            return None;
        }

        // Find the tree with the smallest root value
        let least_index = self.roots.iter().enumerate()
            .filter(|(_, tree)| tree.is_some())
            .min_by_key(|(_, tree)| &tree.as_ref().unwrap().value)
            .map(|(i, _)| i)?;

        // Remove the least_tree from the heap
        let mut least_tree = self.roots[least_index].take()?;

        // Construct a fake heap containing the data in the least tree
        let subtrees = std::mem::take(&mut least_tree.subtrees);
        let mut fake_heap = BinomialHeap {
            heap_type: self.heap_type.clone(),
            num_values: 0,
            roots: subtrees.into_iter().map(Some).collect(),
        };

        // Merge subtrees of least tree back into the heap
        if self.merge(&mut fake_heap) {
            // Merge successful
            // Update the number of values
            self.num_values -= 1;

            // Return the value of the least tree
            Some(least_tree.value)
        } else {
            // Add the least tree back
            self.roots[least_index] = Some(least_tree);

            // Pop failed
            None
        }
    }
}